import java.util.*;

public class ExhaustiveAlgorithm extends PathAlg {
	public void runAlgorithm() {
		HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
		visited.put(0, true);
		AlgRet newPath = visitRest(visited, new int[] { 0 });
		this.expectedLatency = newPath.expectedLatency;
		this.path = newPath.path;
	}

	private AlgRet visitRest(HashMap<Integer, Boolean> visited, int[] prePath) {
		AlgRet ret = null;

		for(int i=0; i<costs.length; i++) {
			if(visited.get(i) == null) {
				// The new, resulting path, after arriving at this node
				int[] pathToHere = new int[prePath.length + 1];
				// Copy previous nodes
				System.arraycopy(prePath, 0, pathToHere, 0, prePath.length);
				// Add current node last
				pathToHere[pathToHere.length - 1] = i;

				// Only leaf nodes calculate path length
				if(pathToHere.length == path.length) {
					return new AlgRet(calculateExpectedLatency(pathToHere), pathToHere);
				}
				else {
					// Mark current node as visited
					visited.put(i, true);

					// Get the shortest path from this node
					AlgRet newPath = visitRest(visited, pathToHere);

					// If this is the shortest, or the first, update return value
					if(ret == null || newPath.expectedLatency < ret.expectedLatency)
						ret = newPath;

					// We're leaving the node
					visited.remove(i);
				}
				
			}
		}
		return ret;
	}
	
	public String getName() {
	    return "Exhaustive";
    }

	private class AlgRet {
		public float expectedLatency; 
		public int[] path;
		public AlgRet(float el, int[] p) { expectedLatency = el; path = p; }
	}
}
